package construction
//给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。
//
//对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。
//
//在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。
//
//实现 TopVotedCandidate 类：
//
//TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
//int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/online-election
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
type TopVotedCandidate struct {
	times   []int
	leader  []int
}
//初始化结构体
func Constructor(persons []int, times []int) TopVotedCandidate {
	var t = TopVotedCandidate{
		times:   times,
	}
	//添加哈希表统计每个人总得票数
	m := make(map[int]int)
	//添加切片，每个时间点的胜利者
	leader := []int{persons[0]}
	for i := 0; i < len(persons); i++ {
		p := persons[i]
		//统计
		if _, ok := m[p]; !ok {
			m[p] = 1
		} else {
			m[p]++
		}
		//计算胜利者是谁，只需和前一个时间点胜利者比较即可
		if i > 0 {
			if leader[i-1] != p && m[leader[i-1]] <= m[p] {
				leader = append(leader, p)
			} else {
				leader = append(leader, leader[i-1])
			}
		}
	}
	t.leader = leader
	return t
}
//计算t时刻的获胜者
func (this *TopVotedCandidate) Q(t int) int {
	i := 0
	for ; i < len(this.times); i++ {
		if this.times[i] > t {
			break
		}
	}
	return this.leader[i-1]
}
